package puzzle.projecteuler.p200;

import java.math.BigInteger;

import astudy.util.AdvMath;

public class Problem133C {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();		
		int max = 100000;
		Integer[] ps = AdvMath.primes(max);
		long sum = 0;
		int count = 0;
		for (int i = 2; i < ps.length; i ++) {//这里检测p=2,3的情形
			int p = ps[i];
			int d = 1;
			int tmp = p-1;
			while (tmp%2 == 0) {
				tmp /= 2;
				d *= 2;
			}
			while (tmp%5 == 0) {
				tmp /= 5;
				d *= 5;
			}
			BigInteger r = BigInteger.TEN.modPow(BigInteger.valueOf(d), BigInteger.valueOf(p));
			if (r.compareTo(BigInteger.ONE) != 0) {
				count ++;
				sum += p;
			}
		}
		sum += 5;	//算上p=2,3
		System.out.println("count = " + count);
		System.out.println("sum = " + sum);
		System.out.println((System.currentTimeMillis() - s) + " ms");
	}
}
